package main

import (
	"fmt"
	q "local/datastructure/queue"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	fmt.Print("前序遍历:")
	preorder(generateTree())
	fmt.Println()
	fmt.Print("中序遍历:")
	midorder(generateTree())
	fmt.Println()
	fmt.Print("后序遍历:")
	tailorder(generateTree())
	fmt.Println()
	fmt.Print("层序遍历:")
	levelorder(generateTree())
}

// 前序遍历(中间元素在前 中左右)
func preorder(node *TreeNode) {
	if node == nil {
		return
	}
	fmt.Printf("%d", node.Val)
	preorder(node.Left)
	preorder(node.Right)
}

// 中序遍历
func midorder(node *TreeNode) {
	if node == nil {
		return
	}
	preorder(node.Left)
	fmt.Printf("%d", node.Val)
	preorder(node.Right)
}

// 后序遍历
func tailorder(node *TreeNode) {
	if node == nil {
		return
	}
	preorder(node.Left)
	preorder(node.Right)
	fmt.Printf("%d", node.Val)
}

// 层序遍历 (借助队列)
func levelorder(node *TreeNode) {
	queue := q.NewQueue()
	queue.Push(node)

	for !queue.IsEmpty() {
		item, err := queue.Pop()
		if err != nil {
			fmt.Println(err)
		}
		fmt.Print(item.(*TreeNode).Val)
		if item.(*TreeNode).Left != nil {
			queue.Push(item.(*TreeNode).Left)
		}

		if item.(*TreeNode).Right != nil {
			queue.Push(item.(*TreeNode).Right)
		}
	}
}

// 构造tree
func generateTree() *TreeNode {
	n1 := &TreeNode{Val: 1, Right: nil, Left: nil}
	n2 := &TreeNode{Val: 2, Right: nil, Left: nil}
	n3 := &TreeNode{Val: 3, Right: nil, Left: nil}
	n1.Left = n2
	n1.Right = n3

	return n1
}
